Introduction to Machine Learning

Unit 20: Clustering (Agglomerative) and Evaluation Metrics

1. Introduction

This unit introduces Clustering, with a focus on hierarchical clustering, particularly Agglomerative Clustering and its linkage methods: single, complete, and average.

Learning Objectives

Today's Agenda

  1. Recap of the Previous Lecture
  2. Discussion on Challenge 2
  3. Neural Network Summary
  4. Python Demo of Hyperparameters of NN
  5. Introduction to Clustering
  6. Partitional vs Hierarchical Clustering
  7. Agglomerative Clustering
  8. Single, Complete and Average Linkages

2. Theory

2.1 Introduction to Clustering

Cluster Analysis is the process of finding similarities among data objects and grouping them into clusters. It is an unsupervised learning method, so no predefined classes are used. A canonical example is Google News, which groups similar news stories.

Clustering Objective A visual explanation of clustering, showing maximized distances between clusters and minimized distances among points within each cluster. MACHINE LEARNING CONCEPT Clustering Objective Inter-cluster distances are maximized Clusters are well-separated from one another MAXIMIZED Cluster A Cluster C Cluster B Intra-cluster distances are minimized Points within the same cluster stay close together CLOSE

2.2 The Notion of a Cluster Can Be Ambiguous

Depending on your viewpoint, the same dataset could be divided into 4 clusters, 2 clusters, or 6 clusters. The "right" answer depends on the context and application, which is one reason clustering evaluation can be subtle.

2.3 Two Major Clustering Paradigms

Partitional Clustering
Hierarchical Clustering
Partitional clustering diagram Original points are separated into three non-overlapping clusters. Partitional Clustering Assigning each point to exactly one cluster Original Points PARTITION A Partitional Clustering C1 C2 C3 K = 3 clusters non-overlapping
Dendrogram hierarchical clustering A hierarchical clustering dendrogram showing all data divided into three clusters, each containing two points. A cut at the indicated level produces three clusters. Dendrogram Hierarchical clustering structure Cut higher → K=1 All Data Cluster A Cluster B Cluster C Cut here → K=3 clusters p1 p2 p3 p4 p5 p6 Horizontal cut determines the number of clusters Hierarchical clustering • visual representation

Side-by-Side Comparison

Aspect Hierarchical Clustering Partitional Clustering (e.g., K-Means)
Number of Clusters No need to specify in advance Some require K (K-Means, K-Medoids); some discover K (DBSCAN, OPTICS, ART)
Result Dendrogram showing nested clusters Single partition of data
Flexibility Can obtain any number of clusters by cutting dendrogram Fixed K clusters
Dataset Size Best for small to medium datasets (< 10,000 points) Suitable for large datasets (millions of points)
Common Applications Biological taxonomy, document organization, gene sequence analysis, social network analysis Customer segmentation, image compression, document clustering, anomaly detection
Deterministic? Yes — same data gives same result Varies: K-Means no, DBSCAN yes

2.4 Types of Hierarchical Clustering

Agglomerative (Bottom-Up)
Divisive (Top-Down)

2.5 Agglomerative Clustering Algorithm

  1. Compute the proximity (distance) matrix between all points.
  2. Let each data point be its own cluster initially.
  3. Repeat:
  4.    a) Merge the two closest clusters.
  5.    b) Update the proximity matrix to reflect the distances from the new merged cluster to the remaining clusters.
  6. Continue until only a single cluster remains (or \(k\) clusters).

The key operation is computing the proximity between two clusters. Different ways of defining this distance lead to different Agglomerative Clustering algorithms.

Aggregating Clusters: Proximity Matrix A proximity matrix for points p1 through p5. The minimum distance is 0.2 between p1 and p2, indicating that they should be merged. AGGREGATING CLUSTERS Proximity Matrix DISTANCE VALUES p1 p2 p3 p4 p5 p1 p2 p3 p4 p5 0 0.2 0.8 0.9 1.1 0.2 0 0.7 0.85 1.05 0.8 0.7 0 0.3 1.2 0.9 0.85 0.3 0 1.15 1.1 1.05 1.2 1.15 0 STEP 1 Nearest pair found Minimum distance p1 ↔ p2 = 0.2 MERGE Action: merge p1 and p2, then recalculate the proximity matrix.

2.6 Inter-Cluster Similarity: Linkage Methods

Given two clusters \( c_i \) and \( c_j \), how do we compute a single distance \( D(c_i, c_j) \) between them? Four common methods are introduced below:

Single Linkage (MIN)
Complete Linkage (MAX)
Average Linkage
Centroid Distance

Definition: Distance between two clusters is the shortest distance between any pair of points, with one point from each cluster.

\[ D(c_i, c_j) = \min_{\substack{a \in c_i \\ b \in c_j}} d(a, b) \]

When merging \( c_k = c_i \cup c_j \), the Lance-Williams update is:

\[ D(c_k, c_l) = \min\{D(c_i, c_l), D(c_j, c_l)\} \]

Susceptible to chaining: a single long bridge of nearby points can merge an entire chain of clusters.

Definition: Distance between two clusters is the greatest distance between any pair of points, with one point from each cluster.

\[ D(c_i, c_j) = \max_{\substack{a \in c_i \\ b \in c_j}} d(a, b) \]

Produces compact, tightly bounded clusters but is sensitive to outliers.

Definition: Distance between two clusters is the average distance over all pairs of points, with one point from each cluster.

\[ D(c_i, c_j) = \frac{1}{|c_i| \cdot |c_j|} \sum_{\substack{a \in c_i \\ b \in c_j}} d(a, b) \]

Update formula for \( c_k = c_i \cup c_j \):

\[ D(c_k, c_l) = \frac{|c_i|}{|c_k|} D(c_i, c_l) + \frac{|c_j|}{|c_k|} D(c_j, c_l) \]

Provides a balanced compromise between single and complete linkage.

Definition: The distance between two clusters is the Euclidean distance between their cluster centroids (mean vectors).

\[ D(c_i, c_j) = d(\mu_i, \mu_j), \quad \mu = \frac{1}{|c|}\sum_{x \in c} x \]

Simple, but it can suffer from inversions.

Linkage Methods Visualized A visual comparison of single, complete, average, and centroid linkage between two clusters. LINKAGE METHODS VISUALIZED How the distance between two clusters is defined Cluster cᵢ cᵢ = {p₁, p₂, p₃} Cluster cⱼ cⱼ = {p₄, p₅} p₁ p₂ p₃ p₄ p₅ MIN distance · Single Link MAX distance · Complete Link Other pairwise distances 3 × 2 = 6 cross-cluster pairs Average Link Mean of all 3 × 2 pairwise distances d(cᵢ, cⱼ) = mean { d(pₖ, pₗ) } Balances every connection between the clusters Centroid Linkage Distance between the two cluster means d(cᵢ, cⱼ) = d( μᵢ, μⱼ ) μᵢ = mean(p₁,p₂,p₃) · μⱼ = mean(p₄,p₅)

3. Interactive Examples

Example 3: Partitional vs Hierarchical Choice

A startup with 100,000,000 customer records wants to create customer segments for marketing. Which clustering approach is more appropriate, and why?

Partitional clustering (K-Means / DBSCAN). Hierarchical clustering has \(O(n^2)\) memory cost for the proximity matrix, which is infeasible for 100M points. Partitional methods are generally more scalable. The flexibility of choosing K post-hoc from a dendrogram is not useful if the hierarchical method cannot be computed at this scale.

Example 4: Linkage Intuition

Two clusters are shaped like two long, thin crescents that touch at one point. Which linkage method will merge them first?

Reveal Answer

Single Linkage (MIN). Because the touching pair has distance ≈ 0, Single Linkage will merge the crescents even if most points in the two crescents are far apart. This is the "chaining effect." Complete Linkage would use the MAX distance (from one crescent tip to the opposite tip) and keep them separate.

4. Numerical Solutions

Problem 1: Agglomerative Clustering — First Merge

Given 5 points with Euclidean distance matrix:

ABCDE
A037911
B306810
C760212
D982013
E111012130

Which pair is merged first in Single Linkage? What is the merge distance?

📘 Step-by-Step Solution

Step 1. Find the smallest non-zero entry in the matrix.

Off-diagonal values: A-B=3, A-C=7, A-D=9, A-E=11, B-C=6, B-D=8, B-E=10, C-D=2, C-E=12, D-E=13.

Step 2. Minimum value = 2, between C and D.

Step 3. Single Linkage uses the minimum distance, so the merge criterion is the smallest non-zero entry.

➡️ First merge: {C, D} at distance 2.

Problem 2: Complete Linkage After Merge

After merging C and D from Problem 1 into cluster CD = {C, D}, compute the distance between CD and the other points (A, B, E) using Complete Linkage (MAX).

📘 Step-by-Step Solution

Step 1. D(CD, A) = max(d(C,A), d(D,A)) = max(7, 9) = 9

Step 2. D(CD, B) = max(d(C,B), d(D,B)) = max(6, 8) = 8

Step 3. D(CD, E) = max(d(C,E), d(D,E)) = max(12, 13) = 13

New distances:

CDABE
CD09813
A90311
B83010
E1311100

Next merge will be A-B at distance 3 (Complete Linkage).

Problem 3: Average Linkage Distance

Cluster X = {p1, p2} and Cluster Y = {q1, q2, q3}. The matrix of pairwise Euclidean distances is:

q1q2q3
p1246
p2357

Compute the Average Linkage distance D(X, Y).

📘 Step-by-Step Solution

Step 1. Count the pairs: |X| = 2, |Y| = 3, so the total number of cross-cluster pairs is 2 × 3 = 6.

Step 2. Sum the six pairwise distances:

\[ \sum d(a,b) = 2 + 4 + 6 + 3 + 5 + 7 = 27 \]

Step 3. Divide the sum by the number of pairs:

\[ D(X,Y) = \frac{27}{6} = 4.5 \]

➡️ Average Linkage distance = 4.5.

5. Try It Yourself

Practice 3: Linkage on 3 Points

Three 1-D points are located at p1 = 0, p2 = 5, and p3 = 9. We start with the singleton clusters {p1}, {p2}, and {p3}.

  1. State the first merge and its distance.
  2. After the first merge, compute the distance from the new cluster to the remaining singleton under: (a) Single Linkage, (b) Complete Linkage, (c) Average Linkage.

1st merge: The pairwise distances are d(p1,p2)=5, d(p2,p3)=4, and d(p1,p3)=9. The minimum is 4, so we merge {p2, p3} at distance 4.

After this merge, we have C23 = {p2, p3} and the singleton {p1}. We now compute D(C23, {p1}) under each linkage method:

\[ \text{(a) Single Linkage} = \min(d(p2,p1), d(p3,p1)) = \min(5, 9) = 5 \] \[ \text{(b) Complete Linkage} = \max(d(p2,p1), d(p3,p1)) = \max(5, 9) = 9 \] \[ \text{(c) Average Linkage} = \frac{5 + 9}{2 \cdot 1} = 7 \]

6. Interactive Quiz

Your score: 0 / 5

7. Key Takeaways

  1. Clustering is unsupervised grouping: maximize inter-cluster distance and minimize intra-cluster distance.
  2. Two paradigms: Partitional (K-Means, DBSCAN — non-overlapping and scalable) versus Hierarchical (dendrogram and nested clusters, generally suited to smaller datasets).
  3. Agglomerative HC starts with singleton clusters and iteratively merges the closest pair using Single (MIN), Complete (MAX), Average, or Centroid linkage.
  4. Single linkage is prone to chaining; Complete linkage favors compact clusters; Average linkage provides a robust middle ground between the two.

8. Common Pitfalls

  1. Applying Agglomerative clustering to 100k+ samples: The proximity matrix requires \(O(n^2)\) memory. For large datasets, consider more scalable partitional methods.
  2. Forgetting Lance-Williams updates: After merging two clusters, update distances using the correct linkage formula; do not re-evaluate all n² distances, which is wasteful and can lose the hierarchical property.
  3. Mis-applying MIN formula: Single Linkage between clusters = min over ALL cross pairs, not just the cluster "representatives."